Abdelaziz Bouteflika telah membesar dan belajar di Maghribi sehingga dia aktif dalam Barisan Pembebasan Kebangsaan (FLN) tahun 1956 ketika umur 19 tahun. Dia mula mengawal dan membuat laporan tentang apa yang berlaku di sempadan Magribi, timur Algeria. Seterusnya dia menjadi setiausaha pentadbiran kepada Houari Boumédiène. Ramai pemimpin dalam Perang Kemerdekaan Algeria menyatakan laporan pembunuhan yang ditulisnya boleh dipertikaikan (baucif).

Pada tahun 1960, Houari Boumédienne mengarahkan Abdelaziz Bouteflika pergi ke Tunisia tetapi tidak tahu di mana dia berada sebenarnya. Selepas mengembara di seluruh Eropah, tindakan disiplin diambil ke atasnya tetapi Houari Boumédienne mempertahankannya. Houari Boumédienne menghantar beliau ke Mali tetapi AbdelAziz menghilangkan diri lagi. Dia muncul semula di Maghribi dengan seorang perempuan. Sekali lagi dimaafkan oleh Houari Boumédienne.

Pada 1962, kemerdekaan dicapai, dia bersama Houari Boumédienne telah membentuk tentera di sempadan dengan sokongan Ahmed Ben Bella menentang kerajaan GPRa.